/*
题目: 公交路线
给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。

    例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。

现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。

求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。

https://leetcode.cn/problems/bus-routes
 */
public class NumBusesToDestination {
    public int numBusesToDestination(int[][] routes, int source, int tar) {
        // 单向
        if (source == tar)  return 0;
        int row = routes.length;

        // 车站  ---  公交车
        Map<Integer, HashSet<Integer>> map = new HashMap<> ();
        for (int i = 0; i < row; i ++) {
            for (int j = 0; j < routes[i].length; j ++) {
                map.putIfAbsent(routes[i][j], new HashSet<> ());
                map.get(routes[i][j]).add(i);
            }
        }

        // 存储下一次 到达 的车站
        Queue<Integer> queue = new LinkedList<> ();
        Set<Integer> visited = new HashSet<> ();
        queue.offer(source);

        int steps = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size -- > 0) {
                // 目前所在车站
                Integer station = queue.poll();
                // 枚举  这个车站上的所有公交车
                Set<Integer> bus = map.get(station);
                // 再记录 公交车 能到的 车站, 下车
                for (Integer cur : bus) {
                    if (visited.contains(cur))  continue ;
                    for (int elem : routes[cur]) {
                        if (elem == tar)    return steps;

                        queue.offer(elem);
                    }
                    visited.add(cur);
                }
            }
            steps ++;
        }

        return -1;
    }
}
